
//316.去除重复字母
class Solution {
public:
    string removeDuplicateLetters(string s) {
        int n=s.size();
        int ch[26]={0};   //存储每个字符出现的次数
        for(auto e:s) ch[e-'a']++;

        string ret;  //用string模拟栈
        int have[26]={0};
        for(int i=0;i<n;i++)
        {
            if(have[s[i]-'a'])   //ret中已经存在该字符了
            {
                ch[s[i]-'a']--;
                continue;
            }
            
            while(!ret.empty()&&ret.back()>s[i]&&ch[ret.back()-'a'])  //将前面字符删除
            {
                have[ret.back()-'a']--;
                ret.pop_back();
            }

            ret.push_back(s[i]);  //将该字符加入
            have[s[i]-'a']++;
            ch[s[i]-'a']--;
        }
        return ret;
    }
};